/*
 * meituan.com Inc.
 * Copyright (c) 2010-2018 All Rights Reserved.
 */
package select;

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

/**
 * <p>
 * 堆排序
 * </p>
 * @author LvJing
 * @version $Id:HeapSort.java v1.0 2018/7/21 上午11:38 LvJing Exp $
 */
public class HeapSort {

    /*
    堆排序：根据堆的定义，若是最大堆，则堆的根节点是最大的数，同时一个节点必然大于其左右子树，所以根据这个定义，把一个待排序数组重建堆，则可以
    选出最大的数，然后排除这个数，从剩余的数中再次重建堆，选出第二大的数，这样就可以实现排序。
    如果是从大到小排序，那么需要每次构建堆时选择出最小的一个数放在最后面，就要使用到最小堆了。
     */

    public void heapSort(int[] arr) {
        if (arr == null || arr.length == 0 || arr.length == 1) {
            return;
        }

        int length = arr.length;
        // 只需排序length-1趟，第length趟只有1个数不用排序
        for (int i = 0; i < length - 1; i++) {
            buildHeap(arr, length - 1 - i);
            swap(arr, 0, length - 1 - i);// 重构堆完成后，第一个数最大，交换后放在当前遍历范围的最后
            System.out.println(Arrays.toString(arr));
        }
    }

    // 对arr数组从0到lastPos构建堆。堆的顺序算是层次遍历
    private void buildHeap(int[] arr, int lastPos) {
        // 从最后一个节点的父节点开始
        for (int i = (lastPos - 1) / 2; i >= 0; i--) {
            int k = i;//正在判断的节点
            // 当前节点的左节点存在
            while (k * 2 + 1 <= lastPos) {
                int biggerPos = k * 2 + 1;

                // 判断biggerPos节点及其相邻节点是否存在
                if (biggerPos < lastPos) {
                    //选出左右节点中更大的一个
                    if (arr[biggerPos] < arr[biggerPos+1]) {
                        biggerPos++;
                    }
                }

                // 如果当前判断节点k小于biggerPos节点（左右节点中更大的一个）
                if (arr[k] < arr[biggerPos]) {
                    swap(arr, k, biggerPos);
                    k = biggerPos;
                } else {
                    break;// 不相等，当前节点k的判断完毕，证明以k为根节点的堆已经正常
                }
            }
        }
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    @Test
    public void test() {
        int[] arr = new int[100];
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(10000) + 1;
        }
        heapSort(arr);
    }
}
